// 给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。
// 你需要让组成和的完全平方数的个数最少。

function numSquares(n: number): number {
  const dp:number[] = new Array(n + 1).fill(0);// 初始化DP矩阵
  for (let i = 1; i <= n; i++) {
    dp[i] = i; // 最差的情况
    for (let j = 2; j * j <= i; j++) {
      dp[i] = Math.min(dp[i], dp[i - j * j] + 1);// 状态转移方程
    }
  }
  return dp[n];
}


// 我们先思考这样一个问题，假设一个数 n 能被拆成 a + b + c + ...
// 而且我们可以保证a 、b 、c的每个数也满足由最少的完全平方数的和组成
// 那么 n 必定也是由最少的完全平方数组合而成的
// 即一个最优复杂的问题，可以被拆成多个相等的最优子问题的和
// 故这道题目也是一道比较经典的动态规划算法的题目
// 首先按照动态规划算法的套路，我们尝试初始化一个DP矩阵
// DP矩阵中的每一个数代表的即是一个状态
// 我们在这里将状态定义为：dp[n]即是和为 n 的由完全平方数组成的个数最少值
// dp[i]的最大值肯定就是i（最不理想的情况下，这个数只能全由 1 组成）
// 由最简单的情况来往上推导（例如 n = 2的情况）
// 状态转移方程即为最坏的情况与 dp[i - j*j] + 1的最小值
// 这里的 “1” 指的就是这个j，而内层循环的条件就是 j * j <= i。
// 最后思考一个边界情况，就是dp的默认值，应该是为 0 
// 原因同样可以由最简单的情况来思考（同样可以思考 n = 2的情况）



